import networkx as nx

# 创建一个有向图
G = nx.DiGraph()

# 添加带有容量的边： (源, 目标, 容量)
G.add_edge('s', 'a', capacity=10)
G.add_edge('s', 'b', capacity=15)
G.add_edge('a', 'b', capacity=5)
G.add_edge('a', 't', capacity=10)
G.add_edge('b', 't', capacity=10)

# 业务流定义（每个业务流：源节点, 宿节点, 带宽需求）
business_flows = [
    {'source': 's', 'sink': 't', 'bandwidth': 12},
    {'source': 's', 'sink': 'a', 'bandwidth': 7},
    {'source': 'a', 'sink': 't', 'bandwidth': 8},
]

# 定义流量分配字典
flow_assignments = {}

# 计算每条链路的流量消耗
link_usage = {edge: 0 for edge in G.edges()}

# 为每个业务流分配带宽
for flow in business_flows:
    source = flow['source']
    sink = flow['sink']
    bandwidth = flow['bandwidth']

    # 计算最大流量
    flow_value, flow_dict = nx.maximum_flow(G, source, sink)

    if flow_value >= bandwidth:
        flow_assignments[(source, sink)] = bandwidth

        # 更新链路上的流量消耗
        for node, flows in flow_dict.items():
            for neighbor, flow in flows.items():
                if flow > 0:
                    link_usage[(node, neighbor)] += flow
        print(f"业务流从 {source} 到 {sink} 已分配带宽 {bandwidth} (最大流量: {flow_value})")
    else:
        print(f"业务流从 {source} 到 {sink} 无法满足带宽需求 {bandwidth} (最大流量: {flow_value})")

# 检查每条链路的流量消耗是否超过容量
print("\n链路流量消耗情况：")
for edge, usage in link_usage.items():
    if usage > G[edge[0]][edge[1]]['capacity']:
        print(f"警告: 链路 {edge} 流量 {usage} 超过了容量 {G[edge[0]][edge[1]]['capacity']}")
    else:
        print(f"链路 {edge} 流量消耗: {usage}/{G[edge[0]][edge[1]]['capacity']}")

# 输出每个业务流的带宽分配情况
print("\n最终带宽分配情况：")
for (source, sink), bandwidth in flow_assignments.items():
    print(f"业务流从 {source} 到 {sink} 的分配带宽: {bandwidth}")
